/**
 * @Project : ProgrammingExercises
 * @Package : Leetcode
 * @File : Q0392.java
 * @Author : WangRuoyu
 * @Date 2023/1/12 15:02
 */

package leetcode;

import java.util.Arrays;

public class Q0392 {

    /**
     * 双指针 O(m+n) O(1)
     **/
//    public boolean isSubsequence(String s, String t) {
//        if (s.isEmpty()) return true;
//        if (s.length() > t.length()) return false;
//        int i = 0;
//        int j = 0;
//        while (j < t.length()) {
//            if (s.charAt(i) == t.charAt(j)) {
//                i++;
//                if (s.length() == i) return true;
//            }
//            j++;
//        }
//        return false;
//    }

    /**
     * 闫氏线性DP O(n) O(n)
     **/
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        if (s.length() > t.length()) return false;
        int f[] = new int[t.length() + 1];
        for (int i = 1; i <= t.length(); i++) {
            f[i] = s.charAt(f[i - 1]) == t.charAt(i - 1) ? f[i - 1] + 1 : f[i - 1];
            if (f[i] == s.length()) return true;
        }
        return false;
    }

    /**
     * 二维dp O(mn) O(mn)
     **/
//    public boolean isSubsequence(String s, String t) {
//        int[][] f = new int[s.length() + 1][t.length() + 1];
//        for (int i = 1; i <= s.length(); i++) {
//            for (int j = 1; j <= t.length(); j++) {
//                if (s.charAt(i - 1) == t.charAt(j - 1)) f[i][j] = f[i - 1][j - 1] + 1;
//                else f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
//            }
//        }
//        return f[s.length()][t.length()] == s.length();
//    }
    public static void main(String[] args) {
        Q0392 sl = new Q0392();
        String s = "abc";
        String t = "ahbgdc";
        System.out.println(sl.isSubsequence(s, t));
    }
}
